Trace modules for generating trace information indicating characteristics of processing performed by a processing apparatus are known. It is possible to generate timestamps indicating the time of generation of trace packets and to insert the timestamps into the trace stream periodically. However, such timestamps use up trace bandwidth since they increase the amount of trace data in the trace stream. If cycle-accurate trace is enabled, then fewer timestamps can be generated, but in this case then more trace data is needed so again this can be expensive in terms of trace buffer capacity and trace port bandwidth. On the other hand, too few timestamps can prevent the order of generation of trace packets from being deduced from the trace streams. The present invention seeks to generate timestamps in an efficient way, in order to reduce the number of trace packets generated by the trace module while still enabling the correlation between trace streams to be established.